package cn.edu.jxau.test;

/**
 * 求链表的长度,考虑有环的情况
 * 
 * @author Fudashi
 */
public class Main {

	public static void main(String[] args) {

		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node8 = new Node(8);
		Node node9 = new Node(8);
		Node node10 = new Node(10);
		Node node11 = new Node(11);
		Node node12 = new Node(12);
		Node node13 = new Node(13);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node7;
		node7.next = node8;
		node8.next = node9;
		node9.next = node10;
		node10.next = node11;
		node11.next = node12;
		node12.next = node13;
		System.out.println(lastK(node1, 14).data);
	}

	public static Node lastK(Node first, int k) {

		Node front = first;
		Node behind = first;
		// 1.front指针移动k次 //
		int i = 0;
		for (; front != null && i < k; i++) {
			front = front.next;
		}
		if (i < k) { // 整个链表不足k个节点
			return null;
		}
		// 2.同步移动 //
		while (front != null) {
			front = front.next;
			behind = behind.next;
		}
		return behind;
	}
}

class Node {

	public int data;
	public Node next;

	public Node(int data) {
		this.data = data;
	}
}